package strings;

/**
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 */
public class N459_RepeatedSubStringPattern {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        int[] next = new int[len];
        getNext(next, s);
        return next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0;
    }

    private void getNext(int[] next, String s) {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1))
                j = next[j];
            if (s.charAt(i) == s.charAt(j + 1))
                j++;
            next[i] = j;
        }
    }

    public static void main(String[] args) {
        N459_RepeatedSubStringPattern solution = new N459_RepeatedSubStringPattern();
        System.out.println(solution.repeatedSubstringPattern("abcdabcdabcd"));

    }
}
